1. Field of the Invention
The present invention relates to passing routing information among mobile intermediate network nodes, such as in a wireless mobile ad hoc network (MANET).
2. Description of the Related Art
Networks of general purpose computer systems and specialized devices connected by external communication links are well known and widely used in commerce. The networks often include one or more network devices that facilitate the passage of information between the computer systems and devices. A network node is a network device or computer or specialized device connected by the communication links. An end node is a node that is configured to originate or terminate communications over the network. An intermediate network node facilitates the passage of data between end nodes.
Communications between nodes are typically effected by exchanging discrete packets of data. Information is exchanged within data packets according to one or more of many well known, new or still developing protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other based on information sent over the communication links. Each packet typically comprises 1] header information associated with a particular protocol, and 2] payload information that follows the header information and contains information that may be processed independently of that particular protocol. In some protocols, the packet includes 3] trailer information following the payload and indicating the end of the payload information. The header includes information such as the source of the packet, its destination, the length of the payload, and other properties used by the protocol. Often, the data in the payload for the particular protocol includes a header and payload for a different protocol associated with a different layer of detail for information exchange. The protocol in the payload is said to be encapsulated in the protocol of the header for the payload.
The headers included in a packet traversing multiple heterogeneous networks, such as the Internet, typically include a physical (layer 1) header, a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
The internetwork header provides information defining the source and destination address within the network. Notably, the path may span multiple physical links. The internetwork header may be formatted according to the Internet Protocol (IP), which specifies IP addresses of both a source and destination node at the end points of the logical path. Thus, the packet may “hop” from node to node along its logical path until it reaches the end node assigned to the destination IP address stored in the packet's internetwork header.
Routers and switches are network devices that determine which communication link or links to employ to support the progress of data packets through the network. A network node that determines which links to employ based on information in the internetwork header (layer 3) is called a router.
Some protocols pass protocol-related information among two or more network nodes in special control packets that are communicated separately and which include a payload of information used by the protocol itself rather than a payload of data to be communicated for another application. These control packets and the processes at network nodes that utilize the control packets are said to be in another dimension, a “control plane,” distinct from the “data plane” dimension that includes the data packets with payloads for other applications at the end nodes.
A link-state protocol is an example of a routing protocol, which only exchanges control plane messages used for routing data packets sent in a different routed protocol (e.g., IP). To reduce the consumption of network resources and improve scalability, some routing protocols divide a large network up into smaller subnetworks. For example, the OSI protocol suite and the Open Shortest Path First (OSPF) routing protocol divide a network into autonomous systems and areas. An autonomous system (AS) is a portion of a network under the network administration of a single authority, such as an enterprise or Internet service provider (ISP). An AS is divided into areas. Each area is a group of contiguous subnetworks and attached end nodes specified by a network administrator, usually manually. In OSI, routers within an AS communicate with each other using an intermediate system to intermediate system (IS-IS) protocol. According to IS-IS, routing within an area (level 1 routing, not to be confused with layer 1, described above, that refers to a physical layer of the OSI model) uses link-state data that distinguishes each link on each router in the area. Routing between areas (level 2 routing) goes through a level 2 router that aggregates the addresses reachable through that level 2 router. By aggregating routing information for addresses reachable over many links of a level 2 router, the amount of network resources consumed to maintain link-state data and make routing decisions can be reduced and network scalability can be enhanced. The division of routers into areas is conventionally a manual process performed by human network administrators.
In an internetwork, networks in different autonomous systems (AS) also route data packets among each other. In general, the network nodes in an autonomous system are manually configured with an Autonomous System identifier (ASID) and pass only further summarized routing information between different AS.
Routing information for an AS is summarized at its boundaries with one or more other ASs at intermediate network nodes called border gateway nodes or border gateway (BG) routers. Routing information shared within the borders of one AS is exchanged using an interior gateway protocol (IGP). Example IGPs include the link state protocols OSPF and IS-IS described above. Another IGP, developed by Cisco Systems of San Jose, Calif. for use in its routers, is the Enhanced Interior Gateway Routing Protocol (EIGRP).
A level 3 routing protocol is used to exchange route summary and routing policy information across AS borders. For example, the Border Gateway Protocol (BGP) is a level 3 routing protocol. The BGP sends summary and policy information between adjacent boundary gateway nodes in different ASs using the External BGP (EBGP). The BGP sends summary and policy information between different boundary gateways in the same AS using the Internal BGP (IBGP).
In situations involving many mobile routers, which can join and depart a network or area using wireless communications links, routers formerly in the same area or autonomous system, may find that one or more links with that area have been broken and the only available links are with routers in other areas. Each router is configured with an area, called herein a configured area or a base area, when the router is configured for routing network communications. Mobile routers are given a base area that matches the base area given to other routers expected to operate closely together because of some affinity that can be identified
According to existing routing protocols, a router, including a mobile router, rejects attempts by an adjacent router that belongs to a different area to initiate an exchange of routing information for the area. Such attempts begin, for example, in OSPF with a HELLO message that includes data that indicates the area to which the router that sends the HELLO message belongs. If that area does not match the area of the receiving router, the receiving router ignores the HELLO message, and any other messages from that area. Clearly, this approach is not suitable in circumstances where the best paths or only paths through a network are through routers belonging to a different area.
In some approaches to use such links, a wireless router is configured with multiple areas. If another router within transmission range belongs to one of the configured areas, the two routers do establish an area adjacency by exchanging HELLO messages, and subsequent routing data for that area is exchanged over that link. The node with multiple areas then maintains full routing information for each of the areas in separate tables. The router is, in essence, a member of both areas and becomes an ABR.
A problem with this approach is that the other router from the different area must communicate only through the particular router configured originally with both areas. It is difficult to ensure that routers with the correct combination of base areas are properly available and located to act as the boundary between the two areas that come together during operation. The manually configured base areas for a router not reflect the actual deployment of a mobile wireless routers, and thus be inappropriate for the available wireless links.
Based on the foregoing, there is a clear need for techniques to utilize links with a router that is in another area or autonomous system, or other domain for sharing routing information at a particular level of detail, that do not suffer the deficiencies of prior approaches.